package algorithm.leetcode.medium;

/*
 给定一个二叉树，它的每个结点都存放一个 0-9 的数字，每条从根到叶子节点的路径都代表一个数字。
 例如，从根到叶子节点路径 1->2->3 代表数字 123。
 计算从根到叶子节点生成的所有数字之和。
 */

/**
 * @author jack.wu
 * @version 1.0
 * @date 2020/10/29
 */
public class Question129 {

    public static void main(String[] args) {

    }

    public int sumNumbers(TreeNode root) {
       return depth(root, 0);
    }

    private int depth(TreeNode node, int preSum) {
        if (node == null) {
            return 0;
        }
        int sum = preSum * 10 + node.val;
        if (node.left == null && node.right == null) {
            return sum;
        }
        return depth(node.left, sum) + depth(node.right, sum);
    }

    private static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }
}
